// Physical memory allocator, intended to allocate
// memory for user processes, kernel stacks, page table pages,
// and pipe buffers. Allocates 4096-byte pages.

#include "types.h"
#include "defs.h"
#include "param.h"
#include "memlayout.h"
#include "mmu.h"
#include "spinlock.h"

void freerange(void *vstart, void *vend);
extern char end[]; // first address after kernel loaded from ELF file
                   // defined by the kernel linker script in kernel.ld
// end 是一个全局变量，它通常在Linux内核的链接脚本（如 kernel.ld）中定义。这个变量表示内核映像的结束地址，即内核从ELF文件加载到内存中后，最后一个字节的地址。
// 按照下面逻辑的推测，end指向的是文件最低的地址

struct run {
  struct run *next;
};

struct {
  struct spinlock lock;
  int use_lock;  //设置是否需要对内存分配器使用锁，置1是需要，0则不需要
  struct run *freelist; // 空闲页的链表，其包含的内存资源只有从内核的 end 到 P2V(PHYSTOP) 之间的 虚拟内存空间
} kmem;

// Initialization happens in two phases.
// 1. main() calls kinit1() while still using entrypgdir to place just
// the pages mapped by entrypgdir on free list.
// 2. main() calls kinit2() with the rest of the physical pages
// after installing a full page table that maps them on all cores.
void
kinit1(void *vstart, void *vend)
{
  initlock(&kmem.lock, "kmem");  //初始化锁
  kmem.use_lock = 0;  //不使用锁。在启动的早期阶段，系统还没有多核或多线程环境，所以不需要锁来同步。
  freerange(vstart, vend);
}

void
kinit2(void *vstart, void *vend)
{
  freerange(vstart, vend);
  kmem.use_lock = 1;  //使用锁。这是因为在这个阶段，系统已经有可能运行在多核或多线程环境中
}

// 将一个范围的内存空间添加进空闲链表中
void
freerange(void *vstart, void *vend)
{
  char *p;
  p = (char*)PGROUNDUP((uint)vstart);//PGROUNDUP 宏函数将虚拟地址 vstart 对齐到页面边界。通常会将地址向上取整到最近的页面大小（通常是4KB）。
                                     //这意味着即使 vstart 不是页面对齐的，p 也会指向包含 vstart 的页面的起始地址。
  for(; p + PGSIZE <= (char*)vend; p += PGSIZE)  //在main函数初始化阶段的kinit1和kinit2函数里调用了这个freerange之后，整个虚拟内存就全部按4KB页大小分割后添加到freelist链表里了
    kfree(p); //一次性free了一整个页面
}
//PAGEBREAK: 21
// Free the page of physical memory pointed at by v,
// which normally should have been returned by a
// call to kalloc().  (The exception is when
// initializing the allocator; see kinit above.)
void
kfree(char *v) //输入虚拟地址
{
  struct run *r;

  if((uint)v % PGSIZE || v < end || V2P(v) >= PHYSTOP) //v必须是PGSIZE的整数倍，v的地址不能小于end（见本c文件最上方）即ELF文件映像的边界，
                                                        //v的物理地址要小于内存最大地址，此处PHYSTOP定义为了0xE000000
    panic("kfree"); //此处是上报错误用的函数

  // Fill with junk to catch dangling refs.
  //填充垃圾数据1，这样做的目的是如果以后有对这块内存的引用（即“悬垂引用”），则可以通过检查垃圾数据来检测到错误。
  memset(v, 1, PGSIZE);  //kfree(char *v)函数相当于一次性free了一整个页面

  //将v这个页添加到空闲链表中，采用头插法。整个过程就是由 [1]<-[2]<-[freelist]  变成  [1]<-[2]<-[3]<-[freelist]
  if(kmem.use_lock)
    acquire(&kmem.lock);
  r = (struct run*)v; //把v强制转换为(struct run*)类型，意思是将v的开头处的一段空间变成结构体run
  r->next = kmem.freelist; //本质就是链表项的动态申请和连接，理解好这个知识点就不难看懂。此处是把v添加到空闲链表中
  kmem.freelist = r;//把空闲链表头更新为最新添加进来的链表项，即头插法动态添加链表项   
  if(kmem.use_lock)
    release(&kmem.lock);
}

// Allocate one 4096-byte page (4KB) of physical memory.  注意申请的是物理内存，但前面建立空闲链表时用的是虚拟地址，网上说是申请一块物理连续的内存页，但返回虚拟地址
// 文档也说了分配器用映射到高内存区域的虚拟地址找到对应的物理页，而非物理地址
    //至于为什么物理内存连续，是因为虚拟内存连续，虚拟内存连续的核心还得归功于kfree在一开始就是连续释放页并构造空闲页链表，镇个系统的内存使用非常有规则，都是申请/释放连续内存页进行使用
// Returns a pointer that the kernel can use.  返回一个内核可以使用的指针
// Returns 0 if the memory cannot be allocated.
char*
kalloc(void)
{
  struct run *r;

  if(kmem.use_lock)
    acquire(&kmem.lock);
  r = kmem.freelist; //从freelist空闲链表的头部开始申请内存
  //根据创建freelist的顺序，感觉这个kalloc是从高地址开始分配内存页的，因此如果内存空了，可能就会返回0（NULL）
  if(r)  //内存地址不为NULL
    kmem.freelist = r->next; //空闲链表指向下一个链表项。  整个过程由 [1]<-[2]<-[3]<-[freelist]  变成  [1]<-[2]<-[freelist]<-[用] 
  if(kmem.use_lock)
    release(&kmem.lock);
  return (char*)r; //空闲页面首地址r在添加进空闲链表时被转换为(struct run*)类型，此处重新转回(char*)
}

